Over the last few years, the number of software applications using 3D images has grown exponentially: online video games, telemedicine, geographic information system, etc. The processing for these applications is made possible by the general availability of ever faster graphics processing units, as well as by the emergence of powerful 3D modeling tools and devices for directly capturing the three dimensional shapes of objects. Consequently, generated 3D content is increasingly rich and detailed.
This content is generally defined by a set of dots or vertices, connected in the form of facets, which are in turn delimited by edges. Such an arrangement is known as “M mesh”.
Faced with this data, whose volume increases rapidly with the new applications for 3D images, the information transmission networks remain very heterogeneous and their bandwidth, although increasing, remains low, in view of the number and volume of files that must be transmitted over these networks, even though it is increasing. Lastly, the platforms designed to receive images of three-dimensional objects are increasingly varied: mobile phones, tablets, micro-computers, PDAs etc.
It is therefore understood that the efficient exchange of complex three-dimensional models over these networks and machines becomes a crucial issue for many industrial applications, including, for example, photorealistic rendering, medical visualization and simulation.
In addition, certain applications that use three-dimensional models, particularly in the fields of medicine and engineering, require lossless recovery of the M Mesh connectivity (i.e. without remeshing) and precise verification of the maximum or mean error rate induced by the compression of its geometry (i.e. the positions and properties associated to the vertices of M).
These considerations explain the requirement for efficient compression methods for three-dimensional meshes, specifically designed for very dense meshes, with near-lossless encoding of the M mesh without remeshing, while providing advanced features such as spatial and quality scalability.
Spatial scalability is defined here as the ability to adjust the resolution of the M mesh to the rendering performance of the image restitution terminal and to the bandwidth available for transmission.
Similarly, quality scalability is defined as the ability to refine the accuracy of the attributes and coordinates progressively, in step with the data stream being decoded.
It is recalled that connectivity coding of is said to be lossless if it preserves the initial triangulation of the original M mesh.
Several techniques are already known in the field of three-dimensional compression.
Among these, the progressive mesh (“PM”) method can be mentioned in particular [Hoppe'96] (Hugues Hoppe, “Progressive meshes”, International Conference on Computer Graphics and Interactive Techniques, 99-108, 1996). In this, as illustrated in FIG. 1, the M mesh evolves by division of one vertex into two vertices or by fusion of two vertices into a single one, and the joint modification of the associated edges and facets (addition or deletion of two facets). This method makes it possible to generate a set of intermediate meshes called Levels of Details or LoD. This representation is suitable for a progressive transfer of the 3D model as well as for View dependent rendering.
However, this method's compression performance is limited and only applies to Oriented manifolds.
In another method, known as Progressive Forest Split (PFS) [Taubin'98] (G. Taubin, A. Guéziec, W. Horn, F. Lazarus, “Progressive forest split compression”, International Conference on Computer Graphics and Interactive Techniques, 123-132, 1998), the mesh is refined by applying splitting operations simultaneously to a set of vertices of the mesh. In the example illustrated in FIG. 2, a vertex is replaced by a set of three vertices, and four new facets are generated as a result. By combining the vertex splitting operations, the PFS approach makes it possible to code these in more compact form, with coarser granularity of the levels of detail as a consequence. Progressive transmission and rendering are achieved again here. The compression performance is better than that of the PM algorithm, but the quality of the levels of detail of the intermediate models is lower.
Another strategy is known as “Patch Coloring” (PC) [Cohen-Or'99] (D. Cohen-Or, D. Levin, O. Remez, “Progressive Compression of Arbitrary Triangular Meshes”, IEEE Visualization Conference Proceedings, 67-72, 1999). In this method, a strategy of facet simplification is used, as illustrated in FIG. 3. This method yields good compression performance and is applicable to all types of meshes. Here again, however, the quality of the levels of detail of the intermediate models is sub-optimal.
Yet another simplification strategy is known as the “Valence-driven decimation approach”. [Alliez'01] (P. Alliez, M. Desbrun, “Progressive encoding for lossless transmission of 3D meshes”, ACM Siggraph Conference Proceedings, 198-205, 2001). In this approach, the vertex decimation strategy utilizes the connectivity of the vertices to minimize the dispersion of the vertices' valences to around the value six, at each intermediate Level of Detail. This method's compression performance is good, but it generates poor quality levels of detail in the case of meshes sampled in an irregular manner. In addition, its application is limited to specific meshes called oriented manifolds.
Compression by octree structure can also be mentioned [Peng'05] (J. Peng, C.-C. J. Kuo, “Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition”, ACM Transactions on Graphics, Vol. 24(3), 609-616, 2005), which yields good compression performance and is applicable to all types of meshes. However, this method provides low-quality levels of detail in the case of smooth 3D meshes.
Lastly, spectral encoding [Karni'01] (Z. Karni, C. Gotsman, “Spectral compression of mesh geometry”, International Conference on Computer Graphics and Interactive Techniques, 279-286, 2000) performs single rate mesh connectivity compression. This information is then utilized to decompose the geometry signal according to a database of functions adapted to the mesh. The compression performance of spectral encoding is good in the case of smooth 3D meshes. However, the calculations are highly complex. In addition, this method only supports quality scalability (the ability to refine the accuracy of the attributes and coordinates progressively, in step with the data stream being decoded).
In summary, the compression techniques that utilize connectivity (i.e. PFS, PC and valence-driven encoding) allow gains in compression compared to the original progressive mesh approach, but at the cost of sub-optimal quality of the intermediate levels of detail. Compression by octree structures uses a simplification criterion that is not suitable for meshes. Lastly, spectral encoding is complex and does not allow spatial scalability.
In [Karni'01], the authors propose utilizing the Touma and Gotsman (TG) technique [Touma'98] (C. Touma, C. Gotsman, “Triangle Mesh Compression”, International Conference on Graphics Interface, 24-34, 1998) in order to encode the connectivity information in single rate (i.e. with no scalability). The TG encoder encodes the mesh connectivity in the form of a sequence of valences. This encoder generates oriented manifolds. The TFAN approach [Mammou'09] (K. Mamou, T. Zaharia, F. Prêteux, “TFAN: A low complexity 3D mesh compression algorithm”, Computer Animation and Virtual Worlds, Vol. 20(2-3), 343-354, 2009) generalizes the TG technique to all types of 3D meshes.